package com.leetcode.dynamic_programming;

import java.util.Arrays;

/**
 * @author Dennis Li
 * @date 2020/7/19 19:30
 */
public class LengthOfLIS_300 {

    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if(len == 0) return 0;
        // dp是以第i个nums数组上的数字结尾的最长子序列的个数
        int[] dp = new int[len];
        // 因为是以i结尾的，而终点不一定是以i结尾，所以需要记录最大值
        int res = 1;
        Arrays.fill(dp, 1);
        // 每一个dp[i]位置上的最长子序列个数不同
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                // 这里的状态方程需要严格定义以nums[i]作为结尾
                if(nums[j] < nums[i])
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    public int lengthOfLIS2(int[] nums) {
        int n = nums.length;
        int[] tails = new int[n];
        int len = 0;
        for (int num : nums) {
            // 二分查找法
            int index = binarySearch(tails, len, num);
            tails[index] = num;
            if(index == len) len++;
        }
        return len;
    }

    private int binarySearch(int[] tails, int len, int key) {
        int l = 0, h = len;
        while (l < h) {
            int mid = l + (h - l) / 2;
            if (tails[mid] == key) {
                return mid;
            } else if (tails[mid] > key) {
                h = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    static class Solution {
        public int lengthOfLIS(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            int len = nums.length;
            int[] dp = new int[len];
            Arrays.fill(dp, 1);
            for (int i = 0; i < len; i++) {
                for (int j = 0; j <= i; j++) {
                    if (nums[i] > nums[j]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
            return Arrays.stream(dp).max().getAsInt();
        }
    }
}

